package leetcode;

/*
680. 验证回文字符串 Ⅱ
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: "aba"
输出: True
示例 2:
输入: "abca"
输出: True
解释: 你可以删除c字符。
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
*/

public class problems_680 {
    public static void main(String[] args) {
        System.out.println(new Solution().validPalindrome("abca"));
    }

    static class Solution {
        public boolean validPalindrome(String s) {
            int left = 0;
            int right = s.length() - 1;
            while (left <= right && left >= 0 && right < s.length()) {
                if (s.charAt(left) != s.charAt(right)) {
                    return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
                }
                left++;
                right--;
            }
            return true;
        }

        /**
         * 回文判断
         */
        public boolean isPalindrome(String s, int left, int right) {
            while (left <= right && left >= 0 && right < s.length()) {
                if (s.charAt(left) != s.charAt(right)) {
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }

//    static class Solution {
//        public boolean validPalindrome(String s) {
//            for (int i = -1; i < s.length(); i++) {
//                if (isPalindrome(s, 0, s.length() - 1, i)) return true;
//            }
//            return false;
//        }
//        /**
//         * 回文判断
//         */
//        public boolean isPalindrome(String s, int left, int right, int ex) {
//            if(left == ex) left++;
//            if(right == ex) right--;
//            while (left <= right && left >= 0 && right < s.length()) {
//                if (s.charAt(left) != s.charAt(right)) {
//                    return false;
//                }
//                left++;
//                right--;
//                if(left == ex) left++;
//                if(right == ex) right--;
//            }
//            return true;
//        }
//    }
    }
}